package sort;

import java.util.Arrays;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName MergeSort.java
 * @Description TODO https://www.jb51.net/article/221479.htm
 * @createTime 2020年09月21日 20:24:00
 */
public class MergeSort  {
	public static void main(String[] args) {
		int[] arr = {1, 12, 3, 13, 14, 2, 44, 4, 56, 7,2};
		sort(arr, 0, arr.length -1);
		System.out.println(Arrays.toString(arr));
		/*System.out.println(1<<15);
		System.out.println(1<<3);
		System.out.println(9/8);
		System.out.println(2/8);*/
	}

	public static int[] sort(int[] a, int low, int high) {
		int mid = (low + high) / 2;
		if (low < high) {
			// 左边归并排序
			sort(a, low, mid);
			// 右边归并排序
			sort(a, mid + 1, high);
			// 合并两个有序数组
			merge(a, low, mid, high);
		}
		return a;
	}

	public static void merge(int[] a, int low, int mid, int high) {
		int[] temp = new int[high - low + 1];
		int i = low;
		int j = mid + 1;
		//临时数组的最后一个有效数据的索引
		int k = 0;
		while (i <= mid && j <= high) {
			// 对比大小，调整顺序
			if (a[i] < a[j]) {
				temp[k++] = a[i++];
			} else {
				temp[k++] = a[j++];
			}
		}
		// 右边剩余元素填充进temp中（因为前面已经归并，剩余的元素必会小于右边剩余的元素）
		while (i <= mid) {
			temp[k++] = a[i++];
		}
		// 右边剩余元素填充进temp中（因为前面已经归并，剩余的元素必会大于于左边剩余的元素）
		while (j <= high) {
			temp[k++] = a[j++];
		}
		// 调整数组顺序
		for (int x = 0; x < temp.length; x++) {
			a[x + low] = temp[x];
		}
	}


	/**
	 *
	 *  最难的是合并,所以可以先完成合并的方法，此方法请参考 基本思想 和 思路分析中的图解来完成
	 *  动脑筋
	 *
	 *
	 *
	 * @param arr   要排序的原始数组
	 * @param left  因为是合并，所以要得到左右两边的的数组信息，这个是左侧数组的第一个索引值
	 * @param mid   因为是一个数组，标识是第一个数组的最后一个索引，即 mid+1 是右侧数组的第一个索引，即中间索引
	 * @param right 右侧数组的结束索引，右边数组的最后一个数
	 * @param temp  临时空间，临时数组
	 */
	public void merge(int[] arr, int left, int mid, int right, int[] temp) {
		// 定时临时变量，用来遍历数组比较
		int l = left;  // 左边有序数组的初始索引
		int r = mid + 1; // 右边有序数组的初始索引
		int t = 0; // temp 数组中当前最后一个有效数据的索引

		// 1. 按思路先将两个数组（有序的）有序的合并到 temp 中
		// 因为是合并两个数组，所以需要两边的数组都还有值的时候才能进行 比较合并
		// 若其中一个数组的值遍历完了（取完了），那么就跳出该循环，把另一个数组所剩的值，直接copy进临时数组即可
		while (l <= mid && r <= right) {
			// 如果左边的比右边的小，则将左边的该元素填充到 temp 中
			// 并移动 t++,l++,好继续下一个
			if (arr[l] < arr[r]) {
				temp[t] = arr[l];
				t++;//移动 temp 临时数组中当前最后一个有效数据的索引
				l++; //左边原始数组的索引移动
			}
			// 否则则将右边的移动到 temp 中
			else {
				temp[t] = arr[r];
				t++;//移动 temp 临时数组中当前最后一个有效数据的索引
				r++;//右边原始数组的索引移动
			}
		}
		// 2. 如果有任意一边的数组还有值，则依序将剩余数据填充到 temp 中
		// 如果左侧还有值
		while (l <= mid) {
			temp[t] = arr[l];
			t++;
			l++;
		}
		// 如果右侧还有值
		while (r <= right) {
			temp[t] = arr[r];
			t++;
			r++;
		}

		// 3. 将 temp 数组，拷贝到原始数组
		// 注意：只拷贝当前temp有效数据到对应的原始数据中，通俗点说，就是原始数组中要排序的数据，通过temp排成了有序的，然后将temp中的有序数据将原始数组中原来要排序的那部分覆盖了就行了
		int tempL = left; // 从左边开始拷贝，左边第一个值的索引
		t = 0;  // temp 中的有效值索引，有效值边界可以通过 right 判定，因为合并两个数组到 temp 中，边界就是 right ，这里自己好好想想
		/*
		 * 对于 8,4,5,7,1,3,6,2 这个数组,
		 * 从栈顶开始合并：8,4 | 5,7       1,3 | 6,2
		 * 先左递归的话：
		 * 第一次：8,4 合并：tempL=0，right=1
		 * 第二次：5,7 合并：tempL=2，right=3
		 * 第三次：4,8 | 5，7 进行合并，tempL=0，right=3
		 * 直到左递归完成，得到左侧一个有序的序列：4,5,7,8 然后再开始递归右边那个无序的
		 * 最后回到栈底分解成两个数组的地方，将两个数组合并成一个有序数组
		 * 这里真的得自己想了，我只能这么说了。
		 */
		System.out.println("tempL=" + tempL + "; right=" + right);
		while (tempL <= right) {
			arr[tempL] = temp[t];
			tempL++;
			t++;
		}
	}


}

